This application claims the priority benefit of Taiwan application serial no. 89105205, filed Mar. 22, 2000.
1. Field of Invention
The present invention relates to a method for searching a database with don""t care fields. More particularly, the present invention relates to a flexible and high-performance packet classification algorithm capable of partitioning packets into sub-tables each having a different data field width and depth. The algorithm is particularly useful for internet router path table lookup and packet classification or serving as a general search engine for a network processor.
2. Description of Related Art
To provide a more flexible service, a router no longer simply performs a search in a routing table followed by redirecting an incoming packet to the next workstation. A current internet switch/router needs to have packet classification capability, the capacity to provide different service quality insurance (QoS) or the capacity to provide processing of data at different safety levels within a virtual private network. In addition, the xe2x80x98firewallxe2x80x99 that ensures network safety also relies on packet classification techniques for granting permission for entering or leaving a network. In other words, many new types of network services depend very much on packet classification.
To achieve high-quality packet classification, the capacity to resolve a packet header is very important. Using the TCP/IP standard as an example, if we decide to use application flow, the 104-bit header that includes an IP Source address (32 bits), an IP destination address (32 bits), a protocol (8 bits), a source port number (16 bits) and destination port number (16 bits) must refer to the rule database in order to determine how to process a packet. In general, the content included in most rule database would permit the network administrator to set up flexible rules for the so-called don""t care fields.
For example, Table No. 1 lists some typical rules (xe2x80x98Xxe2x80x99 refers to a don""t care field).
Due to the increasing importance of packet classification, a number of articles related to search algorithms have been published in international journals. For example, V. Srinivasan et al. (V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, xe2x80x9cFast and Scalable Layer 4 Switching.xe2x80x9d ACM SIGCOMM"" 98, Vancouver, British Columbia) have proposed a cross-product search method. T. V. Lakshman et al. (T. V. Lakshman and D. Stiliadis, xe2x80x9cHigh-Speed Policy-Based Packet Forwarding Using Efficient Multi-dimension Range Matching.xe2x80x9d ACM SIGCOMM"" 98, Vancouver, British Columbia) have proposed using five memory banks to search 1024 rules. N. Mckeown et al. (N. Mckeown, xe2x80x9cPacket Classification on Multiple Fields.xe2x80x99 Inforcomm 2000) has proposed a compress algorithmic method via rule property observation. However, all these conventional methods are low in performance or use vast quantities of storage in the worst case scenarios. Moreover, the conventional methods are unsuitable for other types of search (such as IP path table). Content addressable memory (CAM) (T. Pei and C. Zukowaki, xe2x80x9cPut Routing Table in Silicon.xe2x80x9d IEEE Network Magazine, pp. 42-50, January 1992) is also one of the techniques for resolving packet classification problems. Yet, the biggest drawback of using CAM is that the memory is quite expensive at present. Furthermore, special circuit design and layout technique must be used if CAM is used. Hence, CAM has still not been widely adopted.
Accordingly, one object of the present invention is to provide a flexible and high-performance packet classification algorithm that involves the conversion of original rule database into a rule mapping table format for storage. The rule mapping table is formed by dividing an input key into a plurality of sub-keys, and then sequentially comparing the ordering of each sub-key with the same sub-key field of each rule. Finally, the results of the comparison (xe2x80x981xe2x80x99 indicates a match while a xe2x80x980xe2x80x99 indicates a mismatch) are stored in the rule mapping table through bit mapping.
According to this invention, if the input key has a width of W bits, each sub-key has G bits and the rule database has N rules, the rule mapping table has a size (S) given by the formula S=(W/G)xc3x97Nxc3x972G (bits) and the minimum amount of memory read out in each search (A) is given by the formula A=(W/G)xc3x97N (bits).
In addition, when grouping state of each sub-key is two, that is, having a width of two (G=2), the smallest rule mapping table can be obtained. Size of the smallest rule mapping table is given by the formula S=(Wxc3x97N)xc3x972 (bits) with a corresponding smallest amount of memory read out given by the formula A=(Wxc3x97N)/2 (bits).
The method of searching the rule mapping table includes extracting every sub-key from the input key, reading out corresponding rule vectors in the rule mapping table using the sub-key values directly as indexes, and carrying out a AND-computation of the rule vectors. The resultant vector after computation is known as a conformed rule vector. If the conformed rule mapping is non-zero, the leftmost bit (assuming that the leftmost rule has the highest priority) representation is taken out to represent the search result. The search result is made to multiply with the size of associated data. Together with the starting address for holding associated data, a data storage address corresponding to the search result can be found.
This invention uses a plurality of search engines all working in parallel to process rule mapping table search operations. Each search engine processes a portion of the rule vector. Meanwhile, the assignments of sub-key fields to each search engine are achieved through an interleave matrix.
Furthermore, the rule mapping table can be dissected into a plurality of sub-tables such that the number of rules and rule width in each sub-table can be set. Each sub-table has an initial scan value register, a terminal scan value register and a register for recording the width of the sub-table. Each sub-table can even have a register for registering the initial address of memory for holding associated data and a register for registering size of storage location for the associated data.
This invention also provides a flexible and high-performance packet classification algorithm that support a plurality of rule databases or sub-tables. In addition, this invention permits the co-existence of a plurality of rule databases each having a different length and width in the same search engine. Therefore, the design can provide actual improvements (higher speed, smaller volume occupation) and flexibility (possible coexistent of different rule databases). Moreover, the invention not only can provide a dynamic setting of different rule width for sub-tables on physical memory units, but can also provide unlimited flexibility to the search algorithm. In brief, the search method of this invention can be used as a general-purpose search engine in the design of network processor or in any situation where rapid search is necessary. The search method can serve even as a replacement technology for CAM.
It is to be understood that both the foregoing general description and the following detailed description are exemplary, and are intended to provide further explanation of the invention as claimed.